/*
 * sort.c
 *
 *  Created on: 07-Feb-2012
 *      Author: Ashok
 */

#include "sort.h"
#include <stdlib.h>
#include <stdio.h>

#define HEAP_LEFT(i) 	(2*i)		/* The left child of the node i */
#define HEAP_RIGHT(i) 	(2*i + 1)	/* The right child of the node i */
#define HEAP_PARENT(i) 	(i/2)		/* The parent of the node i */


static void mergeSortRt(int *in, int p, int r);
static void merge(int *in, int low, int mid, int high);
static void quickSortRt(int *in, int p, int r);
static void buildHeap(int *in, int inSize);
static void maxHeapify(int *in, int heapSize, int i);
static void quickSortPartition(int *in, int p, int r, int *q, int *t);
static void quickSortRandomPartition(int *in, int p, int r, int *q, int *t);
static void quickSortMedianPartition(int *in, int p, int r, int *q, int *t);
static subArr_t maxSArrRt(int *in, int p, int r);
static subArr_t maxSArrCross(int *in, int low, int mid, int high);

static int noOfInversions;

/* All input values must be less than this value */
#define MAX_INPUT 1501

/* All input values must be greater than this value */
#define MIN_INPUT -1501

void insertionSort(int *in, int inSize) {
	int key, prev, keyVal;
	if(inSize > 1) {
		for(key = 1; key < inSize; key++) {
			keyVal = in[key];
			prev = key - 1;
			while((prev >= 0) && (in[prev] > keyVal)) {
				in[prev+1] = in[prev];
				prev--;
			}
			in[prev+1] = keyVal;
		}
	}
}


void insertionSort_1(int *in, int inSize) {
	int key, prev, tmp, flag;
	if(inSize > 1) {
		for(key = 1; key < inSize; key++) {
			/* Key is smaller than the largest value in the sorted list
			 * left of the key */
			if(in[key] < in[key-1]) {
				tmp = in[key];
				flag = 0;
				/* Find a position for the key in the array left of the key */
				for(prev = key; prev > 0; prev--) {
					if(tmp >= in[prev-1]) {
						in[prev] = tmp;
						flag = 1;
						break;
					}
					else {
						in[prev] = in[prev-1];
					}
				}
				/* if we parsed till the first element and still all numbers are
				 * greater than the key */
				if(flag == 0) {
					in[0] = tmp;
				}
			}
		}
	}
}

void mergeSort(int *in, int inSize) {
	noOfInversions = 0;
	mergeSortRt(in, 0, inSize-1);
	printf("No of inversions: %d\n", noOfInversions);
}

static void mergeSortRt(int *in, int p, int r){
	int q = (p+r)/2;
	if(p < r){
		mergeSortRt(in, p, q);
		mergeSortRt(in, q+1, r);
		merge(in, p, q, r);
	}
}

static void merge(int *in, int low, int mid, int high){
	int l1, l2; /* Lengths of the 2 arrays */
	int *ar1, *ar2; /* Arrays to temporarily hold the two halves */
	int i,j,k;	/* Index */
	l1 = mid - low + 1; /* From Low to Mid */
	l2 = high - mid;	/* From Mid+1 to High */
	ar1 = (int*)malloc((l1+1) * sizeof(int)); /* +1 for the max element */
	ar2 = (int*)malloc((l2+1) * sizeof(int)); /* +1 for the max element */
	/* Copy the input halves into 2 separate temporary buffers */
	for(i = 0; i < l1; i++)
		ar1[i] = in[i+low];
	ar1[i] = MAX_INPUT;
	for(i = 0; i < l2; i++)
		ar2[i] = in[i+mid+1];
	ar2[i] = MAX_INPUT;
	j = 0; /* Init the buffer indexes */
	k = 0;
	for(i=low; i < (low + l1 + l2); i++) {
		if(ar1[j] < ar2[k]) {
			in[i] = ar1[j];
			j++;
		}
		else {
			in[i] = ar2[k];
			k++;
			noOfInversions++;
		}
	}
	free(ar1);
	free(ar2);
}


void quickSort(int *in, int inSize){
	quickSortRt(in, 0, inSize-1);
}

/* Quick sort recursion function
 * Inputs:
 * in	-> Input array reference
 * p	-> Lower index of array
 * r	-> Upper index of array
 * Description:
 * Recursively sorts the input array using the quick sort algorithm
 */
static void quickSortRt(int *in, int p, int r){
	int q, t; /* p <= q <= t <= r; such that in[p..q-1]<in[q..t]<in[t+1..r]
									and all values in in[q..t] are equal */
	if((r-p) > 1){
		quickSortRandomPartition(in, p, r, &q, &t);
		quickSortRt(in, p, q-1);
		quickSortRt(in, t+1, r);
		/* array in[q..t] has all values as equal hence no need for sorting */
	}
}

/* Partitioning function for the quick sort routine
 * Inputs:
 * in	-> Input array reference
 * p	-> Lower index of array
 * r	-> Upper index of array
 * Outputs:
 * int q,t -> The position of the pivot that partitions the array. (p <= q <= t <= r)
 */
static void quickSortPartition(int *in, int p, int r, int *q, int *t){
	int pPos, pivot, i, j, k, temp;
	pPos = r; /* pPos is the pivot position. We take the last element as the pivot */
	pivot = in[pPos];
	/* Initialisation conditions
	 * Both j and i point to illegal values
	 * Hence both the virtual arrays (<= pivot & >= pivot) given by [p..i] and [i..j]
	 * respectively are empty initially
	 */
	j = p;
	i = p-1;
	k = p-1;
	for(; j < r; j++){
		/* Loop invariant
		 * The elements of the array in[p..i] is always < pivot
		 * The elements of the array in[i+1..t] is always == pivot
		 * The elements of the array in[t+1..j-1] is always > pivot
		 * The elements of the array in[j..pPos-1] need to be analysed yet
		 * The value in[pPos] == pivot always
		 */
		if(in[j] <= pivot){
			k++;
			if(in[j] == pivot){
				temp = in[k];
				in[k] = in[j];
				in[j] = temp;
			}
			else {
				i++;
				temp = in[j];
				in[j] = in[k];
				in[k] = in[i];
				in[i] = temp;
			}
		}
	}
	k++;	/* After increment k points to the first element of the array with value > pivot */
	i++;	/* After increment k points to the first element of the array with value == pivot */
	temp = in[k];	/* Reposition the pivot to the pivot position by swapping with above pointed element*/
	in[k] = pivot;
	in[r] = temp;
	*q = i;
	*t = k;
}

/* Partitioning function for the quick sort routine
 * Inputs:
 * in	-> Input array reference
 * p	-> Lower index of array
 * r	-> Upper index of array
 * Outputs:
 * int q,t -> The position of the pivot that partitions the array. (p <= q <= t <= r)
 */
static void quickSortRandomPartition(int *in, int p, int r, int *q, int *t){
	int pPos, pivot, i, j, k, temp;
	pPos = (rand() % (r-p)) + p; /* pPos is the pivot position. We take the last element as the pivot */
	temp = in[pPos];
	in[pPos] = in[r];
	in[r] = temp;
	pivot = in[r];
	/* Initialisation conditions
	 * Both j and i point to illegal values
	 * Hence both the virtual arrays (<= pivot & >= pivot) given by [p..i] and [i..j]
	 * respectively are empty initially
	 */
	j = p;
	i = p-1;
	k = p-1;
	for(; j < r; j++){
		/* Loop invariant
		 * The elements of the array in[p..i] is always < pivot
		 * The elements of the array in[i+1..t] is always == pivot
		 * The elements of the array in[t+1..j-1] is always > pivot
		 * The elements of the array in[j..pPos-1] need to be analysed yet
		 * The value in[pPos] == pivot always
		 */
		if(in[j] <= pivot){
			k++;
			if(in[j] == pivot){
				temp = in[k];
				in[k] = in[j];
				in[j] = temp;
			}
			else {
				i++;
				temp = in[j];
				in[j] = in[k];
				in[k] = in[i];
				in[i] = temp;
			}
		}
	}
	k++;	/* After increment k points to the first element of the array with value > pivot */
	i++;	/* After increment k points to the first element of the array with value == pivot */
	temp = in[k];	/* Reposition the pivot to the pivot position by swapping with above pointed element*/
	in[k] = pivot;
	in[r] = temp;
	*q = i;
	*t = k;
}


void heapSort(int *in, int inSize){
	int heapSize, i, temp;
	inSize = inSize - 1; /* For index from [0..inSize-1] */
	heapSize = inSize;
	buildHeap(in, inSize);
	for(i = inSize; i > 0; i--){
		temp = in[0];
		in[0] = in[i];
		in[i] = temp;
		heapSize--;
		maxHeapify(in, heapSize, 0);
	}
}

static void buildHeap(int *in, int inSize){
	int i;
	/* We will apply max-heapify property from 0 to n/2 elements
	 * because the elements n/2 + 1 to n are the leaves and are max-heaps by themselves
	 */
	for(i = (inSize/2); i >= 0; i--){
		maxHeapify(in, inSize, i); /* Heap size = input array size, since we want to heapify the entire array */
	}

}

/* Function to apply the maximum heap property to the element at index i of array
 * Inputs:
 * in	-> Input array
 * i	-> The element at the position i for which the max-heapify has to be done
 */
static void maxHeapify(int *in, int heapSize, int i){
	int l, r, temp;
	int max;
	l = HEAP_LEFT(i);
	r = HEAP_RIGHT(i);
	max = i;
	if((l <= heapSize) && (in[l] > in[max]))
		max = l;
	if((r <= heapSize) && (in[r] > in[max]))
		max = r;
	if(max != i){
		temp = in[i];
		in[i] = in[max];
		in[max] = temp;
		maxHeapify(in, heapSize, max);
	}
}


/* Finds the maximum sub array using a linear method
 * Inputs:
 * in		-> input array reference
 * inSize	-> size of the input array
 * Description:
 * The function uses a brute force method to find all sub array with the maximum sub of values
 * This function is a linear method function and has theta(n^2) performance
 */
subArr_t maxSubArrayLinear(int *in, int inSize) {
	subArr_t maxSArr, curSArr;
	maxSArr.stIdx = 0;
	maxSArr.endIdx = 0;
	maxSArr.sArrVal = -1;
	for(curSArr.stIdx = 0; curSArr.stIdx < inSize; curSArr.stIdx++){
		curSArr.sArrVal = 0;
		for(curSArr.endIdx = curSArr.stIdx; curSArr.endIdx < inSize; curSArr.endIdx++){
			curSArr.sArrVal += in[curSArr.endIdx];
			if(curSArr.sArrVal > maxSArr.sArrVal){
				maxSArr.sArrVal = curSArr.sArrVal;
				maxSArr.stIdx = curSArr.stIdx;
				maxSArr.endIdx = curSArr.endIdx;
			}
		}
	}
	return maxSArr;
}

/* Finds the maximum sub array in linear time
 * Inputs:
 * in		-> input array reference
 * inSize	-> input array size
 * Description:
 * The function finds the maximum sub array in a[0..inSize-1] in theta(inSize) time
 * This function uses the Kadane's Algorithm to do this
 */
subArr_t maxSubArrayLinTime(int *in, int inSize) {
	int prevMax, newMax, i, newStIdx;
	subArr_t max;
	/* Since there is at least one positive element the minimum value of the maximum sub array is 0 */
	prevMax = newMax = 0;
	for(i = 0; i < inSize; i++){
		if((newMax + in[i]) > 0){
			newMax = newMax + in[i];
		}
		else{
			newMax = 0;	/* This element of the array is so low, that we can start afresh */
			newStIdx = i+1; /* The maximum sub array will start from the next element */
		}
		/* See if the maxSubArr till the previous element is greater than
		 * the maxSubArr that we computed above that includes the current element
		 * then assign the biggest value as the maxSubArr till the current element */
		if(newMax > prevMax){
			prevMax = newMax;
			max.stIdx = newStIdx;
			max.endIdx = i;
		}
	}
	max.sArrVal = prevMax;
	return max;
}


/* Finds the maximum sub array using a recursive method
 * Inputs:
 * in		-> input array reference
 * inSize	-> size of the input array
 */
subArr_t maxSubArrayRecursive(int *in, int inSize) {
	return maxSArrRt(in, 0, inSize-1);
}

/* Find the maximum sub array recursively
 * Inputs:
 * in 	-> input Array reference
 * p	-> lower index of the array
 * r	-> upper index of the array
 * Description:
 * Function finds the maximum sub array in the array in[p..r]
 */
static subArr_t maxSArrRt(int *in, int p, int r) {
	subArr_t max, lMax, rMax, cMax;
	int q;
	if(p == r) {
		max.stIdx = p;
		max.endIdx = r;
		max.sArrVal = in[p];
		return max;
	}
	else {
		q = (p + r)/2;
		lMax = maxSArrRt(in, p, q);
		rMax = maxSArrRt(in, q+1, r);
		cMax = maxSArrCross(in, p, q, r);
		if((lMax.sArrVal >= rMax.sArrVal) && (lMax.sArrVal >= cMax.sArrVal)) {
			return lMax;
		}
		else if((rMax.sArrVal >= lMax.sArrVal) && (rMax.sArrVal >= cMax.sArrVal)) {
			return rMax;
		}
		else {
			return cMax;
		}
	}
}

/* Find the maximum sub array for sub arrays that cross the middle value
 * Inputs:
 * in	-> input array reference
 * low	-> the lower index of the array
 * mid	-> the middle point over which the sub array formed shall cross
 * high	-> the upper index of the array
 * Description:
 * The functions finds the maximum sub array in the array in[p..r] such that
 * the sub array's lower index is in [p..q] and
 * the sub array's upper index is in [q+1..r] where
 * p = low, q = mid, r = high
 */
static subArr_t maxSArrCross(int *in, int low, int mid, int high) {
	subArr_t max;
	int i, lSum, rSum, lMax, rMax;
	lSum = 0;
	rSum = 0;
	lMax = rMax = MIN_INPUT;
	/* Find the maximum sub array to the left of the middle value
	 * trick is since we include the middle value in the calculation of the maximum
	 * the time taken is linear
	 */
	for(i = mid; i >= low; i--){
		lSum += in[i];
		if(lSum > lMax){
			lMax = lSum;
			max.stIdx = i;
		}
	}
	/* Do the same for the right of the middle value */
	for(i = mid+1; i <= high; i++){
		rSum += in[i];
		if(rSum > rMax){
			rMax = rSum;
			max.endIdx = i;
		}
	}
	max.sArrVal = lMax + rMax;
	return max;
}
